package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/next-greater-element-ii/">503. 下一个更大元素 II</a>
 */
public class Solution503 extends BaseSolution {

    public int[] nextGreaterElements(int[] nums) {
        int[] stack = new int[nums.length];
        int top = -1;
        stack[++top] = Arrays.stream(nums).max().getAsInt();

        int[] rst = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != stack[top]) {
                continue;
            }
            rst[i] = -1;
            int p = (i + nums.length - 1) % nums.length;
            for (; ; p = (p - 1 + nums.length) % nums.length) {
                while (nums[p] > stack[top]) {
                    top--;
                }
                if (nums[p] < stack[top]) {
                    rst[p] = stack[top];
                    stack[++top] = nums[p];
                } else {
                    if (top == 0) {
                        rst[p] = -1;
                        break;
                    } else {
                        rst[p] = stack[top - 1];
                    }
                }
            }
        }
        return rst;
    }

    public static void main(String[] args) {
        Solution503 solution = new Solution503();
        printVals(solution.nextGreaterElements(new int[] {
                1,2,3,4,3
        }));
    }
}